1327. Ладьи на шахматной доске

Ещё в детстве маленького Гарика заинтересовал вопрос: сколькими способами на шахматной доске размером n × n можно расставить n ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил – бросил шахматы.

А как быстро Вы управитесь с этой задачкой?

Вход. Размер шахматной доски n (n ≤ 1000).

Выход. Выведите ответ, найденный Гариком.

Пример входа	Пример выхода
2	2

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Первую ладью можно поставить на любую из n клеток первой строки. Вторую ладью можно поставить на любую из n – 1 клеток второй строки (ее нельзя ставить в тот столбец, где уже стоит первая ладья). Третью ладью можно поставить на любую из n – 2 клеток третьей строки и так далее. Всего имеется n! расстановок ладей так чтобы они не били друг друга.

Поскольку n ≤ 1000, то для вычисления n! следует воспользоваться длинной арифметикой.

Реализация алгоритма

import java.util.*;

import java.math.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

BigInteger res = BigInteger.ONE;

for(int i = 1; i <= n; i++)

res = res.multiply(BigInteger.valueOf(i));

System.out.println(res);

con.close();

}

}